{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Words Obtained After Adding a Letter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wordCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计追加字母可以获得的单词数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong> 开始的字符串数组 <code>startWords</code> 和 <code>targetWords</code> 。每个字符串都仅由 <strong>小写英文字母</strong> 组成。</p>\n",
    "\n",
    "<p>对于 <code>targetWords</code> 中的每个字符串，检查是否能够从 <code>startWords</code> 中选出一个字符串，执行一次 <strong>转换操作</strong>&nbsp;，得到的结果与当前&nbsp;<code>targetWords</code> 字符串相等。</p>\n",
    "\n",
    "<p><strong>转换操作</strong> 如下面两步所述：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><strong>追加</strong> 任何 <strong>不存在</strong> 于当前字符串的任一小写字母到当前字符串的末尾。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>例如，如果字符串为 <code>\"abc\"</code> ，那么字母 <code>'d'</code>、<code>'e'</code> 或 <code>'y'</code> 都可以加到该字符串末尾，但 <code>'a'</code> 就不行。如果追加的是 <code>'d'</code> ，那么结果字符串为 <code>\"abcd\"</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li><strong>重排</strong> 新字符串中的字母，可以按 <strong>任意</strong> 顺序重新排布字母。\n",
    "\t<ul>\n",
    "\t\t<li>例如，<code>\"abcd\"</code> 可以重排为 <code>\"acbd\"</code>、<code>\"bacd\"</code>、<code>\"cbda\"</code>，以此类推。注意，它也可以重排为 <code>\"abcd\"</code> 自身。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ol>\n",
    "\n",
    "<p>找出 <code>targetWords</code> 中有多少字符串能够由&nbsp;<code>startWords</code> 中的 <strong>任一</strong> 字符串执行上述转换操作获得。返回<em> </em><code>targetWords</code><em> </em>中这类 <strong>字符串的数目</strong> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你仅能验证 <code>targetWords</code> 中的字符串是否可以由 <code>startWords</code> 中的某个字符串经执行操作获得。<code>startWords</code>&nbsp; 中的字符串在这一过程中 <strong>不</strong> 发生实际变更。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>startWords = [\"ant\",\"act\",\"tack\"], targetWords = [\"tack\",\"act\",\"acti\"]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "- 为了形成 targetWords[0] = \"tack\" ，可以选用 startWords[1] = \"act\" ，追加字母 'k' ，并重排 \"actk\" 为 \"tack\" 。\n",
    "- startWords 中不存在可以用于获得 targetWords[1] = \"act\" 的字符串。\n",
    "  注意 \"act\" 确实存在于 startWords ，但是 <strong>必须</strong> 在重排前给这个字符串追加一个字母。\n",
    "- 为了形成 targetWords[2] = \"acti\" ，可以选用 startWords[1] = \"act\" ，追加字母 'i' ，并重排 \"acti\" 为 \"acti\" 自身。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>startWords = [\"ab\",\"a\"], targetWords = [\"abc\",\"abcd\"]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "- 为了形成 targetWords[0] = \"abc\" ，可以选用 startWords[0] = \"ab\" ，追加字母 'c' ，并重排为 \"abc\" 。\n",
    "- startWords 中不存在可以用于获得 targetWords[1] = \"abcd\" 的字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= startWords.length, targetWords.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= startWords[i].length, targetWords[j].length &lt;= 26</code></li>\n",
    "\t<li><code>startWords</code> 和 <code>targetWords</code> 中的每个字符串都仅由小写英文字母组成</li>\n",
    "\t<li>在 <code>startWords</code> 或 <code>targetWords</code> 的任一字符串中，每个字母至多出现一次</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-words-obtained-after-adding-a-letter](https://leetcode.cn/problems/count-words-obtained-after-adding-a-letter/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-words-obtained-after-adding-a-letter](https://leetcode.cn/problems/count-words-obtained-after-adding-a-letter/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"ant\",\"act\",\"tack\"]\\n[\"tack\",\"act\",\"acti\"]', '[\"ab\",\"a\"]\\n[\"abc\",\"abcd\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, start_words: List[str], target_words: List[str]) -> int:\n",
    "        bs = set()\n",
    "        for s in start_words:\n",
    "            b = 0\n",
    "            for c in s:\n",
    "                b |= 1 << ord(c) - ord('a')\n",
    "            bs.add(b)\n",
    "        ans = 0\n",
    "        for t in target_words:\n",
    "            b = 0\n",
    "            for c in t:\n",
    "                b |= 1 << ord(c) - ord('a')\n",
    "            for c in t:\n",
    "                if b ^ (1 << ord(c) - ord('a')) in bs:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def getmask(word):\n",
    "            ans = 0\n",
    "            for ch in word:\n",
    "                ans |= 1 << (ord(ch) - ord('a'))\n",
    "            return ans\n",
    "        \n",
    "        masks = set()\n",
    "        for start in startWords:\n",
    "            masks.add(getmask(start))\n",
    "\n",
    "        ans = 0\n",
    "        for target in targetWords:\n",
    "            mask = getmask(target)\n",
    "            for ch in target:\n",
    "                if mask ^ (1 << (ord(ch) - ord('a'))) in masks:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        mapping = {}\n",
    "        for tword in targetWords:\n",
    "            k = ''.join(sorted(tword))\n",
    "            if(k not in mapping):\n",
    "                mapping[k] = 1\n",
    "            else:\n",
    "                mapping[k] += 1\n",
    "        result = 0\n",
    "        for sword in startWords:\n",
    "            for i in range(26):\n",
    "                c = chr(i+ord('a'))\n",
    "                if(c not in sword):\n",
    "                    tmp = ''.join(sorted(sword + c))\n",
    "                    if(tmp in mapping):\n",
    "                        result += mapping[tmp]\n",
    "                        del mapping[tmp]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def getmask(word):\n",
    "            ans = 0\n",
    "            for ch in word:\n",
    "                ans |= 1 << (ord(ch) - ord('a'))\n",
    "            return ans\n",
    "        \n",
    "        # 利用startWords构建哈希集合\n",
    "        s = set()\n",
    "        for word in startWords:\n",
    "            mask = getmask(word)\n",
    "            s.add(mask)\n",
    "        \n",
    "        ans = 0\n",
    "        # 枚举targte中的词删除一个已有字母后，是否在哈希集合中\n",
    "        # 需要注意满足条件后需要break\n",
    "        for word in targetWords:\n",
    "            mask = getmask(word)\n",
    "            # 枚举取消每个字符\n",
    "            for ch in word:\n",
    "                if mask ^ (1 << (ord(ch) - ord('a'))) in s:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        s = set()\n",
    "        # 将每一个单词的二进制数保存下来\n",
    "        for word in startWords:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch)-ord('a'))\n",
    "            s.add(mask)\n",
    "        # 统计结果\n",
    "        ans = 0\n",
    "        for word in targetWords:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch)-ord('a'))\n",
    "            for ch in word:\n",
    "                if mask ^(1 << (ord(ch)-ord('a'))) in s:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        # 用二进制数表示startWords和targetWords中的单词\n",
    "        d = set()\n",
    "        for word in startWords:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c)-ord('a'))\n",
    "            d.add(mask)\n",
    "        # 去查询targetWords中的单词去掉一个字母是否会出现在startWords中\n",
    "        ans = 0\n",
    "        for word in targetWords:\n",
    "            # 统计\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c)-ord('a'))\n",
    "            # 枚举去掉一个单词\n",
    "            for c in word:\n",
    "                if mask^(1 << (ord(c)-ord('a'))) in d:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        cnt = Counter()\n",
    "        for w in targetWords:\n",
    "            cnt[''.join(sorted(list(w)))] += 1\n",
    "        \n",
    "        res = set()\n",
    "        for w in startWords:\n",
    "            for ch in ascii_lowercase:\n",
    "                if ch not in w:\n",
    "                    t = ''.join(sorted(w + ch))\n",
    "                    if cnt[t]:\n",
    "                        res.add(t)\n",
    "\n",
    "        return sum(cnt[t] for t in res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        s = set()\n",
    "        for word in startWords:\n",
    "            a = list(word)\n",
    "            a.sort()\n",
    "            s.add(''.join(a))\n",
    "        res = 0\n",
    "        for word in targetWords:\n",
    "            a = list(word)\n",
    "            a.sort()\n",
    "            n = len(a)\n",
    "            for i in range(n):\n",
    "                if (i == 0 or a[i] != a[i-1]) and (i == n - 1 or a[i] != a[i+1]):\n",
    "                    if ''.join(a[:i]) + ''.join(a[i+1:]) in s:\n",
    "                        res += 1\n",
    "                        break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        # 简简单单\n",
    "        cnt = 0\n",
    "        startWords = set(''.join(sorted(w)) for w in startWords)\n",
    "        for word in  targetWords:\n",
    "            s = ''.join(sorted(word))\n",
    "            for i in range(len(s)):\n",
    "                if s[:i] + s[i+1:] in startWords:\n",
    "                    cnt += 1\n",
    "                    break\n",
    "                \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def f(x):\n",
    "            a = 0\n",
    "            for c in x:\n",
    "                t = ord(c)-ord('a')\n",
    "                a |= 1 << t\n",
    "            return a\n",
    "        \n",
    "        startWords = {f(w) for w in startWords}\n",
    "\n",
    "        s = 0\n",
    "\n",
    "        for w in targetWords:\n",
    "            for i in range(len(w)):\n",
    "                if f(w[:i] + w[i+1:]) in startWords:\n",
    "                    s += 1\n",
    "                    break\n",
    "        \n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        s = set()\n",
    "        for word in startWords:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch) - ord('a'))\n",
    "            s.add(mask)\n",
    "        ans = 0\n",
    "        for word in targetWords:\n",
    "            mask = 0\n",
    "            print(\"word\",word)\n",
    "            # 计算整个单词的掩码\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch) - ord('a'))\n",
    "            for ch in word:\n",
    "                if mask ^ (1 << (ord(ch) - ord('a'))) in s:  # 去掉这个字符\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        # 位运算来实现字符的记录\n",
    "        has = set()\n",
    "        ans = 0\n",
    "        for s in startWords:\n",
    "            mask = 0\n",
    "            for c in s:\n",
    "                mask |= (1 << (ord(c) - ord('a')))\n",
    "            has.add(mask)\n",
    "        for s in targetWords:\n",
    "            mask = 0\n",
    "            for c in s:\n",
    "                mask |= (1 << (ord(c) - ord('a')))\n",
    "            for c in s:\n",
    "                if (mask ^ (1 << (ord(c) - ord('a')))) in has:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        s = set()\n",
    "        for word in startWords:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch) - ord('a'))\n",
    "            s.add(mask)\n",
    "        ans = 0\n",
    "        for word in targetWords:\n",
    "            mask = 0\n",
    "            print(\"word\",word)\n",
    "            # 计算整个单词的掩码\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch) - ord('a'))\n",
    "            for ch in word:\n",
    "                if mask - (1 << (ord(ch) - ord('a'))) in s:  # 去掉这个字符\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        ''' \n",
    "        只能进行追加而不能去掉\n",
    "        不能追加相同的字符\n",
    "        在 startWords 或 targetWords 的任一字符串中，每个字母至多出现一次\n",
    "        '''\n",
    "        #set():使用add(key)往集合中添加元素，重复的元素自动过滤\n",
    "        startWords_set=set()\n",
    "        #向里面添加startwords的二进制元素\n",
    "        for i in range(len(startWords)):\n",
    "            sum = 0\n",
    "            for j in startWords[i]:\n",
    "                sum |= 1<<(ord(j) - 97)\n",
    "            startWords_set.add(sum)\n",
    "        ans=0\n",
    "        for i in range(len(targetWords)):\n",
    "            sum = 0\n",
    "            for j in targetWords[i]:\n",
    "                sum |= 1<< (ord(j) -97)\n",
    "                #去掉该字符\n",
    "            for j in targetWords[i]:\n",
    "                if sum ^ (1 << (ord(j)-97)) in startWords_set:\n",
    "                    ans+=1\n",
    "                    break\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        n = len(startWords)\n",
    "        status = set()\n",
    "        for x in startWords:\n",
    "            s = 0\n",
    "            for c in x:\n",
    "                s |= 1 << (ord(c) - ord('a'))\n",
    "            status.add(s)\n",
    "\n",
    "        ret = 0\n",
    "        for x in targetWords:\n",
    "            s = 0\n",
    "            for c in x:\n",
    "                s |= 1 << (ord(c) - ord('a'))\n",
    "            for i in range(26):\n",
    "                if s & 1 << i and (s ^ 1 << i) in status:\n",
    "                    ret += 1\n",
    "                    break\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def f(s):\n",
    "            state = 0\n",
    "            for ch in s:\n",
    "                state |= 1 << (ord(ch) - ord('a'))\n",
    "            return state\n",
    "        \n",
    "        s = set()\n",
    "        for w in startWords:\n",
    "            s.add(f(w))\n",
    "        ans = 0\n",
    "        for w in targetWords:\n",
    "            state = f(w)\n",
    "            for i in range(26):\n",
    "                if state & 1 << i:\n",
    "                    if state & ~(1 << i) in s:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        # 用二进制数表示startWords和targetWords中的单词\n",
    "        d = set()\n",
    "        for word in startWords:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c)-ord('a'))\n",
    "            d.add(mask)\n",
    "        # 去查询targetWords中的单词去掉一个字母是否会出现在startWords中\n",
    "        ans = 0\n",
    "        for word in targetWords:\n",
    "            # 统计\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c)-ord('a'))\n",
    "            # 枚举去掉一个单词\n",
    "            for c in word:\n",
    "                cnt = mask\n",
    "                cnt ^= 1 << (ord(c)-ord('a'))\n",
    "                if cnt in d:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        st = set()\n",
    "        for word in startWords:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch) - ord('a'))\n",
    "            st.add(mask)\n",
    "\n",
    "        ans = 0\n",
    "        seen = defaultdict(int)\n",
    "        for word in targetWords:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= 1 << (ord(ch) - ord('a'))\n",
    "            if mask in seen:\n",
    "                ans += seen[mask]\n",
    "                continue\n",
    "            for ch in word:\n",
    "                if mask ^ (1 << (ord(ch) - ord('a'))) in st:\n",
    "                    ans += 1\n",
    "                    seen[mask] = 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        st_set = set()\n",
    "        for startWord in startWords:\n",
    "            c = 0\n",
    "            for w in startWord:\n",
    "                c ^= 1 << (ord(w)-ord('a'))\n",
    "            st_set.add(c)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for targetWord in targetWords:\n",
    "            c = 0\n",
    "            for w in targetWord:\n",
    "                c ^= 1 << (ord(w)-ord('a'))\n",
    "            for w in targetWord:\n",
    "                if c ^ (1 << (ord(w)-ord('a'))) in st_set:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, s: List[str], t: List[str]) -> int:\n",
    "        st = set()\n",
    "        for w in s:\n",
    "            mask = 0\n",
    "            for c in w:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            st.add(mask)\n",
    "        print(st)\n",
    "        ans = 0\n",
    "        for w in t:\n",
    "            mask = 0\n",
    "            for c in w:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            for c in w:\n",
    "                if mask ^ (1 << (ord(c) - ord('a'))) in st:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        d = set()\n",
    "        \n",
    "        for wordi in startWords:\n",
    "            mask = 0\n",
    "            for si in wordi:\n",
    "                mask |= 1 << (ord(si) - ord('a'))\n",
    "            d.add(mask)\n",
    "\n",
    "        print(d,2 >> 1)\n",
    "        ans = 0\n",
    "        for twordi in targetWords:\n",
    "            maski = 0\n",
    "            for ti in twordi:\n",
    "                maski |= 1 << (ord(ti) - ord('a'))\n",
    "            for ti in twordi:\n",
    "                if maski ^ (1 << (ord(ti) - ord('a'))) in d:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def mask(word):\n",
    "            res = 0\n",
    "            for ch in word:\n",
    "                res |= 1 << (ord(ch) - ord('a'))\n",
    "            return res\n",
    "        \n",
    "        masks = set()\n",
    "        for start in startWords:\n",
    "            msk = mask(start)\n",
    "            for i in range(26):\n",
    "                # 该位没有\n",
    "                if (msk >> i) & 1 == 0:\n",
    "                    masks.add(msk | (1 << i))\n",
    "        \n",
    "        ans = 0\n",
    "        for target in targetWords:\n",
    "            if mask(target) in masks:\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def mask(word: str) -> int:\n",
    "            res = 0\n",
    "            for ch in word:\n",
    "                res |= 1<<(ord(ch) - ord('a'))\n",
    "            return res\n",
    "        masks = set()\n",
    "        for start in startWords:\n",
    "            msk = mask(start)\n",
    "            for i in range(26):\n",
    "                if((msk >> i) & 1) == 0:\n",
    "                    masks.add(msk | (1 << i))\n",
    "        cnt = 0\n",
    "        for target in targetWords:\n",
    "            if (mask(target) in masks):\n",
    "                cnt += 1\n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        # 将 word 转化为表示包含字母状态的二进制整数\n",
    "        def mask(word: str) -> int:\n",
    "            res = 0\n",
    "            for ch in word:\n",
    "                res |= 1 << (ord(ch) - ord('a'))\n",
    "            return res\n",
    "        \n",
    "        masks = set()   # 所有可以获得的状态\n",
    "        for start in startWords:\n",
    "            # 遍历初始单词，根据其状态值构造所有可以获得的状态\n",
    "            msk = mask(start)\n",
    "            for i in range(26):\n",
    "                if ((msk >> i) & 1) == 0:\n",
    "                    masks.add(msk | (1 << i))\n",
    "        cnt = 0   # 可以获得的单词数\n",
    "        for target in targetWords:\n",
    "            if mask(target) in masks:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        # target = defaultdict(set)\n",
    "        # ans = 0\n",
    "        # def mask(word):\n",
    "        #     a = 0\n",
    "        #     for i in word:\n",
    "        #         a |=  1<< (ord(i)-ord('a'))\n",
    "        #     return a\n",
    "        # for startWord in startWords:\n",
    "        #     a = mask(startWord)\n",
    "        #     for i in range(26):\n",
    "        #         if ((a >> i) & 1) == 0:\n",
    "        #             target[len(startWord)+1].add(a| (1<<i))\n",
    "\n",
    "        # for targetWord in targetWords:\n",
    "        #     if target[len(targetWord)]:\n",
    "        #         a = mask(targetWord)\n",
    "        #         if a in target[len(targetWord)]:\n",
    "        #             ans+=1\n",
    "        \n",
    "        # return ans\n",
    "\n",
    "        # 将 word 转化为表示包含字母状态的二进制整数\n",
    "        def mask(word: str) -> int:\n",
    "            res = 0\n",
    "            for ch in word:\n",
    "                res |= 1 << (ord(ch) - ord('a'))\n",
    "            return res\n",
    "        \n",
    "        masks = set()   # 所有可以获得的状态\n",
    "        for start in startWords:\n",
    "            # 遍历初始单词，根据其状态值构造所有可以获得的状态\n",
    "            msk = mask(start)\n",
    "            for i in range(26):\n",
    "                if ((msk >> i) & 1) == 0:\n",
    "                    masks.add(msk | (1 << i))\n",
    "        cnt = 0   # 可以获得的单词数\n",
    "        for target in targetWords:\n",
    "            if mask(target) in masks:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def getmask(word):\n",
    "            ans = 0\n",
    "            for ch in word:\n",
    "                ans |= 1 << (ord(ch) - ord('a'))\n",
    "            return ans\n",
    "        \n",
    "        s = set()\n",
    "        # 枚举startWords,可构成的集合\n",
    "        for word in startWords:\n",
    "            mask = getmask(word)\n",
    "            for i in range(26):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    s.add(mask | (1 << i))\n",
    "        \n",
    "        ans = 0\n",
    "        for word in targetWords:\n",
    "            if getmask(word) in s:\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help(self, startWords:List[str], word:str):\n",
    "        n=len(word)\n",
    "        cnt=collections.Counter(word)\n",
    "        for sw in startWords:\n",
    "            if len(sw)>n-1:\n",
    "                break\n",
    "            if len(sw)==n-1:\n",
    "                t=0\n",
    "                flag=True\n",
    "                for ch,val in cnt.items():\n",
    "                    if ch not in sw:\n",
    "                        if val!=1:\n",
    "                            flag=False\n",
    "                            break\n",
    "                        t+=1\n",
    "                        if t>1:\n",
    "                            flag=False\n",
    "                            break\n",
    "                    else:\n",
    "                        if sw.count(ch)!=val:\n",
    "                            flag=False\n",
    "                            break\n",
    "                if flag and t==1:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def wordCount1(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        startWords.sort(key=lambda x:len(x))\n",
    "        res=0\n",
    "        for word in targetWords:\n",
    "            if len(startWords[-1])<len(word)-1 or len(startWords[0])>=len(word):\n",
    "                continue\n",
    "            if self.help(startWords,word):\n",
    "                res+=1\n",
    "        return res\n",
    "\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def mask(word:str):\n",
    "            res=0\n",
    "            for ch in word:\n",
    "                res|=1<<(ord(ch)-ord('a'))\n",
    "            return res\n",
    "        \n",
    "        masks=set()\n",
    "        for start in startWords:\n",
    "            msk=mask(start)\n",
    "            for i in range(26):\n",
    "                if ((msk>>i)&1)==0:\n",
    "                    masks.add(msk|(1<<i))\n",
    "        cnt=0\n",
    "        for target in targetWords:\n",
    "            if mask(target) in masks:\n",
    "                cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        target = set()\n",
    "        ans = 0\n",
    "        def mask(word):\n",
    "            a = 0\n",
    "            for i in word:\n",
    "                a |=  1<< (ord(i)-ord('a'))\n",
    "            return a\n",
    "        for startWord in startWords:\n",
    "            a = mask(startWord)\n",
    "            n = len(startWord)\n",
    "            for i in range(26):\n",
    "                if ((a >> i) & 1) == 0:\n",
    "                    target.add(a| (1<<i))\n",
    "\n",
    "        for targetWord in targetWords:\n",
    "            a = mask(targetWord)\n",
    "            if a in target:\n",
    "                ans+=1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        target = defaultdict(set)\n",
    "        ans = 0\n",
    "        def mask(word):\n",
    "            a = 0\n",
    "            for i in word:\n",
    "                a |=  1<< (ord(i)-ord('a'))\n",
    "            return a\n",
    "        for startWord in startWords:\n",
    "            a = mask(startWord)\n",
    "            n = len(startWord)\n",
    "            for i in range(26):\n",
    "                if ((a >> i) & 1) == 0:\n",
    "                    target[n+1].add(a| (1<<i))\n",
    "\n",
    "        for targetWord in targetWords:\n",
    "            n = len(targetWord)\n",
    "            if target[n]:\n",
    "                a = mask(targetWord)\n",
    "                if a in target[n]:\n",
    "                    ans+=1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        target = defaultdict(set)\n",
    "        ans = 0\n",
    "        def mask(word):\n",
    "            a = 0\n",
    "            for i in word:\n",
    "                a |=  1<< (ord(i)-ord('a'))\n",
    "            return a\n",
    "        for startWord in startWords:\n",
    "            a = mask(startWord)\n",
    "            for i in range(26):\n",
    "                if ((a >> i) & 1) == 0:\n",
    "                    target[len(startWord)+1].add(a| (1<<i))\n",
    "\n",
    "        for targetWord in targetWords:\n",
    "            if target[len(targetWord)]:\n",
    "                a = mask(targetWord)\n",
    "                if a in target[len(targetWord)]:\n",
    "                    ans+=1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        target = defaultdict(set)\n",
    "        ans = 0\n",
    "        def mask(word):\n",
    "            a = 0\n",
    "            for i in word:\n",
    "                a |=  1<< (ord(i)-ord('a'))\n",
    "            return a\n",
    "        for startWord in startWords:\n",
    "            a = mask(startWord)\n",
    "            n = len(startWord)\n",
    "            for i in range(26):\n",
    "                if ((a >> i) & 1) == 0:\n",
    "                    target[n+1].add(a| (1<<i))\n",
    "\n",
    "        for targetWord in targetWords:\n",
    "            n = len(targetWord)\n",
    "            if target[n]:\n",
    "                a = mask(targetWord)\n",
    "                if a in target[n]:\n",
    "                    ans+=1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        def f(s):\n",
    "            state = 0\n",
    "            for ch in s:\n",
    "                state |= 1 << (ord(ch) - ord('a'))\n",
    "            return state\n",
    "\n",
    "        cnt = Counter()\n",
    "        for s in startWords:\n",
    "            state = f(s)\n",
    "            for i in range(26):\n",
    "                if state & 1 << i == 0:\n",
    "                    cnt[state | 1 << i] += 1\n",
    "\n",
    "        return sum(bool(cnt[f(t)]) for t in targetWords)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        zhan=set()\n",
    "        zimu=[chr(x+ord('a')) for x in range(0,26)]\n",
    "        # print(zimu)\n",
    "        for i in startWords:\n",
    "            for j in zimu:\n",
    "                if j not in i:\n",
    "                    tem=i+j\n",
    "                    tem=''.join(sorted(tem))\n",
    "                    zhan.add(tem)\n",
    "        # print(zhan)\n",
    "        # print(len(zhan))\n",
    "        res=0\n",
    "        for i in targetWords:\n",
    "            i=''.join(sorted(i))\n",
    "            if i in zhan:\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        a=set()\n",
    "        for s in startWords:\n",
    "            for c in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                if c not in s:\n",
    "                    a.add(''.join(sorted(s+c)))\n",
    "        return sum(''.join(sorted(i)) in a for i in targetWords)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:\n",
    "        possible_words=set()\n",
    "        alphabets = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "        for startWord in startWords:\n",
    "            for char in alphabets:\n",
    "                if char not in startWord:\n",
    "                    temp2=startWord+char\n",
    "                    temp1=list(temp2)\n",
    "                    temp1.sort()\n",
    "                    temp=''.join(temp1)\n",
    "                    if temp not in possible_words:\n",
    "                        possible_words.add(temp)\n",
    "        res=0\n",
    "        # print(possible_words)\n",
    "        for targetWord in targetWords:\n",
    "            temp1=list(targetWord)\n",
    "            temp1.sort()\n",
    "            temp=''.join(temp1)\n",
    "            print(temp)\n",
    "            if temp in possible_words:\n",
    "                res+=1\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
